package com.LeeCode;

import java.util.HashMap;

/**
 * 可互换矩形的组数
 */

public class Code2001 {
    public static void main(String[] args) {
        int[][] rectangles = {
                {4, 8}, {3, 6}, {10, 20}, {15, 30}
        };
        System.out.println(new Code2001().interchangeableRectangles(rectangles));
    }

    public long interchangeableRectangles(int[][] rectangles) {
        long ans = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for (int[] rectangle : rectangles) {
            int x = rectangle[0];
            int y = rectangle[1];
            int gcd = gcd(x, y);
            String key = x/gcd + "," + y/gcd;
            ans += map.getOrDefault(key, 0);
            map.merge(key, 1, Integer::sum);
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }
}
